#include <vector>
#include <algorithm>
using namespace std;
class Solution
{
public:
    int minFallingPathSum(vector<vector<int>> &matrix)
    {
        // 状态表示:dp[i][j] 走到这一格的最小下降和
        // 状态转换方程: dp[i][j]=min(dp[i-1][j-1],dp[i-1][j],dp[i-1]p[j+1]);
        //              如果所依赖其他状态不存在则视作INT_MAX
        // 初始化: dp=matrix[i]
        vector<vector<int>> dp(matrix);
        for (int i = 1; i < dp.size(); i++)
        {
            for (int j = 0; j < dp[i].size(); j++)
            {
                int up_min = INT_MAX;
                for (int k = j - 1; k <= j + 1; k++)
                    up_min = min(k >= 0 && k < dp[i].size() ? dp[i - 1][k] : INT_MAX, up_min);
                dp[i][j] += up_min;
            }
        }
        return *min_element(dp.back().begin(), dp.back().end());
    }
};